Data in a network such as the Internet is generally sent from a source to a destination in blocks which are usually referred to as packets or datagrams, these terms generally being used interchangeably. In order to allow communication, via the Internet, between source points and destination points irrespective of whether or not they have previously communicated, a protocol known as an Internet Protocol (IP) is used. This is a data-oriented protocol used by source and destination hosts, or servers, for communicating data across a packet-switched network in order to ensure that no specific set-up process is needed before a host acting for a source tries to send packets to a host acting for the intended destination or destinations, irrespective of whether or not they have previously communicated, and irrespective of the type of data that is being communicated. Internet Protocol is a protocol relating to how certain types of information may be included in a specific manner in a “header” associated with the packets. It precedes the data in the packets, and allows them to be routed from source to the correct destination via the Internet.
Internet Protocol Headers
With reference to FIG. 1, headers associated with datagrams according to the current version of the Internet Protocol, known as IPv4, comprise a first 4-bit field indicating this version. The second field is a 4-bit “Internet Header Length” (IHL) field indicating the number of 32-bit words in the IPv4 header. The following 8 bits have been allocated to a “Differentiated Services” field containing the 6 bit Differentiated Services Code Point (DSCP) and the 2 bit “ECN” (Explicit Congestion Notification) field. The DSCP allows it to be specified how the datagram should be handled as it makes its way through the network (i.e. low delay, high priority etc.). The ECN field is set probabilistically at a congested resource so that, over a series of packets, the destination can infer the level of congestion of the path traversed. The next 16-bit IPv4 field defines the entire datagram size, including header and data, in 8-bit bytes. The minimum-length datagram is 20 bytes and the maximum is 65535.
The next field is a 16-bit “Identification” field. This field has primarily been used for unique identification of fragments of an original IP datagram. It has been suggested that this field could be used for other purposes, such as for adding packet-tracing information to datagrams. A 3-bit “Flags” field follows which is used to control or identify fragments. This is followed by a 13-bit “Fragment Offset Field” which allows a receiver to determine the position of a particular fragment in the original IP datagram.
The next field is an 8-bit “Time-To-Live” (TTL) field, which aims to prevent datagrams from persisting (e.g. going around in loops) within a network. Historically the TTL field limited a datagram's lifetime in seconds, but it has come to be a “hop count” field, with some attempt to maintain the original meaning by hops across large distances making themselves appear as multiple hops. The value may initially set at 255. Each packet switch (or router) that the datagram crosses decrements the TTL field by one (or maybe more at interfaces to long distance links). If the TTL field hits zero before reaching its intended destination, the packet is no longer forwarded by a packet switch and is thus discarded.
An 8-bit Protocol field follows. This field defines the next protocol used in the data portion of the IP datagram. The Internet Assigned Numbers Authority maintains a list of Protocol numbers. Common protocols include ICMP, TCP and UDP.
The following field in an IPv4 datagram header is a 16-bit “Checksum” field. Some values in a IPv4 datagram header may change at each packet switch hop, so the checksum may need to be adjusted on its way through a network. The checksum is followed by 32-bit “Source Address” and a 32-bit “Destination Address” fields respectively.
Additional header fields (called “Options”) may follow the destination address field, but these are not often used.
Reliability in a Network
It should be noted that the Internet Protocol itself does not provide or guarantee a reliable datagram service, but a “best effort” service—it makes almost no guarantee that packets will reach their destination. Packets may arrive damaged, out of order, duplicated, or may be dropped entirely. In order to provide reliability in a network, there may also be a “Transport” layer. This is responsible for end-to-end error recovery and flow control, and aims to ensure complete data transfer, although this again cannot be guaranteed for any of a variety of reasons relating to capacity, infrastructure problems, abuse etc. In the IP protocol Stack this function is achieved by the connection oriented Transmission Control Protocol (TCP). Alternatively a basic datagram service can be provided by the User Datagram Protocol (UDP).
Routing in a Network
Between source points and destination points in a network, there are generally multiple intermediate points, some of which may be active, in the sense that they may take a role in the decision-making regarding the route by which data they receive is forwarded on towards the destination. In the context of the Internet, these may be known as packet switches, or Internet routers. Other intermediate points may be passive, in the sense that they take no part in this decision-making—data may simply pass via them on its way through the network. Intermediate points that are “active” in the above sense may look at information in or associated with the data, in particular the destination address, in order to determine the subsequent path, or at least the next leg of the path, that the data should take in order to proceed towards its destination. In addition to such decision-making in respect of a specific item of data, intermediate points may communicate continuously with each other in order to share information about network conditions. Typically this information concerns the number of hops to each destination network and may include other information such as policies concerning whether one network wishes to offer routing transit to another. Intermediate points may also continuously share information about more pathological network conditions, such as infrastructure problems, congestion levels and delays occurring at different areas within the network. It should be noted that “areas” in the context of a network need not be areas in the geographical, or even the sense of a physically interconnected set of nodes—they may be areas of connectivity in a virtual network overlaid on the real physical links, which simply have a function to perform or a service to provide, much as the Internet is a network of virtual links overlaid on lower layer physical links.
Routing decisions may be taken in order to balance the load across different areas of a network, or to route data around a problem area. In addition to this, if the network is being run on a commercial basis, with charges being made for services provided, routing decisions may be taken in order to find the cheapest, fastest, or most reliable route through the network. In relation to this, various schemes, such as “congestion charging” schemes, operate or have been proposed for determining how such charges could or should be levied, but there are significant problems in setting up a system which is workable and fair, not least because for a data packet to leave a sender and reach its destination, it may need to pass through parts of one or more networks which may be of a variety of different types (i.e. fixed, ad hoc etc.). These may extend through several different countries or via satellites, be under the control of different entities, or conform to a variety of different sets of rules, both technical and legal. For a charging scheme to operate successfully in such circumstances, it may need to be able to operate irrespective of levels of trust between entities, and may need to be resistant to abuse or dishonest behaviour by any entities involved.
A recent example of a routing algorithm that claims to attempt to optimise throughput of a network by taking account of node metrics indicative of congestion levels is disclosed in United States patent application US2003/0128687 (“Worfolk et al), but this does not take any account of possible abuse or dishonesty by parties who may or may not trust one another.
Charging Schemes in a Network
Charging schemes based on the Explicit Congestion Notification (ECN) field have been proposed. If the ECN capability is enabled by the sender (after negotiation with the receiver) the 2-bit ECN field is initialised to a binary value of either 01 or 10 (which are considered equivalent for the purposes of congestion control). The ECN field may be set to binary 11 (congestion experienced—CE) by any router through which a data packet passes, depending probabilistically on the levels of congestion currently being experienced by that router. When the data reaches its destination, the relative proportion of packets set to CE may provide an indication to the receiver of the overall level of congestion on the path by which the data passed through the network. This may be interpreted as a “cost” associated with the delivery of data via that particular path, which may be allocated to the receiving entity, the sending entity, or one or more other entities. Irrespective of whether any entity truly pays any consideration, the information available to the receiver may be of use in allowing routing decisions to be taken. It will be noted however that for any other entity to take any action or decision based on the final value, they generally need to be able to rely on the receiving entity to have passed on correct information.
In the literature that is supportive of using congestion charging of the above type, the problem of only the receiver being able to pay congestion charges or rely directly on information based on Explicit Congestion Notification data has generally been dismissed by arguing that arrangements between sender and receiver are a separate problem. This problem has been used as an argument against congestion charging, but no attempts at solving this problem are apparent in the literature.
Co-Pending Un-Published UK Patent Applications
Co-pending UK patent applications GB 0407144 (filed 30 Mar. 2004 and having Agent's Ref. A30432) and GB 0407381 (filed 31 Mar. 2004 and having Agent's Ref. A30499), both of which are unpublished at the time of filing of the present application, relate to data networks, and to nodes making up parts of data networks, arranged to derive information relating to the characterisation of paths taken by data travelling between nodes in the networks. Path characterisation information is fed back from a receiver of data to a provider of data, and allows nodes subsequently forwarding data to be informed of characteristics of the downstream path. The applications also relate to routing nodes and methods for using such path characterisation information to make informed routing decisions when forwarding data in a data network. The content of these two applications is incorporated herein by reference.
The insight that measures of characteristics of the downstream path can be used as a “shadow price” is discussed in the above un-published co-pending UK patent applications, and is of relevance to the reason why embodiments of the inventions to which those applications relate are capable of providing solutions to various problems relating to path characterisation, routing and congestion control. A “shadow price” can be thought of as a proxy for a market price. Within its environment or system, it can be regarded as and used as an actual price, even though it may not have any actual commercial status outside that environment or system. A brief summary of the concept behind the subject matter of these applications is given below.
The sender in a network such as datagram network can be thought of as being active, whereas the receiver may be passive, in the following sense. A node capable of sending items may be able to control what it sends, where it tries to send them, and how often it sends them, but it has very little control over what, from where or how often it receives items. On the other hand, a sender is generally in the worst natural position to know about the network it is sending items into, while a node receiving items may at least have the benefit of being able to receive information characterising the path taken by arriving items (path congestion, hops traversed etc). In this regard, the sender can be thought of as having control without knowledge, whereas the receiver has knowledge without control. There is thus a benefit in a receiver providing feedback to the sender in respect of the path knowledge it learns, in order to carry path knowledge to where the control is. This is how the Internet currently works. Herein lie two problems:                (i) if the receiver has no incentive to feed back the information, and to feed it back honestly, it may well not do so;        (ii) intermediate nodes are both receivers and senders (in the sense that forwarding is simply sending something that has been received), but end to end feedback only conveys path knowledge to the first sender on the path, and does not convey path knowledge to every intermediate sender. Although the Internet is based on the end-to-end principle, where intermediate nodes are not expected to exercise intelligent control, they are often expected to make intelligent forwarding decisions based on routing information, which essentially should comprise knowledge of the downstream path. They may also be expected to make decisions on the rate at which they forward different classes of data, which would also ideally be informed by downstream path knowledge.        
The two afore-mentioned un-published co-pending UK patent applications disclose solutions, amongst others, to one or both of two general problems, which can be regarded as separate but related. These problems can be summarised as follows:                1) How to arrange for the provision of information to nodes characterising the downstream path from those node; and        2) How to proof this information from falsification.        
Embodiments disclosed in those applications allow the following to be achieved:                1) Provision of path characterisation information to nodes in a network, said information relating to any of a variety of possible characteristics of the path or paths downstream of the node in question. To achieve this, there may be no need for upstream traffic beyond that being fed back end-to-end from a destination of data to the appropriate source. This is particularly useful where routes are asymmetric, particularly where it is not possible to send data upstream over certain unidirectional links (e.g. satellite links). But it is also useful if the available capacity can be increased by removing the overhead of routing information.        2) Ensuring that information such as the above may be proofed against falsification for the gain of an individual controlling any intermediate or end node.Reacting to Congestion in a Network        
In certain circumstances, when a node in a network becomes congested or overloaded, there may be a need for it to drop some packets, or forward some packets with a lower priority than others, or otherwise to subject some packets to a process that is more beneficial to the sender and/or receiver than that to which other packets are subjected. Various schemes have been proposed or are being used which allow nodes in a network to drop packets in such circumstances.
The main ways in which available capacity of routers, nodes, or other types of network resources can be shared among users or flows can be summarised according to the following four types: fairly, differentiated, by reservation admission and by dynamic willingness to pay. Outstanding problems exist in relation to each of these when tackled under current approaches, as will be outlined below.
Fairness: If a router is arbitrating service by only considering rate fairness locally, it will not be able to allow for flows that are constrained by downstream congestion. So schemes that penalise the highest rate flows cannot discriminate between real misbehaviour and flows which would genuinely be allocated a high rate because slower flows cannot make use of any more capacity. And schemes that maximise the minimum rate do not optimise network fill because they are not taking into account downstream congestion. Indeed, recent research suggests that max-min fairness can lead to pathologically poor allocations in some asymmetric cases. Or in other words, given proportional fairness has been proven to optimise welfare, anything else must be less optimal. But proportional fairness requires knowledge of downstream path congestion. In TCP congestion control, senders rely on congestion feedback (drop or ECN) to equalise the products of bandwidth, delay and the square root of path congestion. Attempts by the network to police TCP fairness are currently hobbled by lack of visibility of the last two parameters, so they tend to merely police rate fairness, leading to false positives and missed negatives. As explained above, embodiments of the un-published co-pending UK patent applications incentivise end systems to report these parameters truthfully into each network path.
Differentiated service: Moving on to differentiated (i.e. unfair) service, the general aim is to ‘colour’ traffic to allow any forwarding resource to understand how it should prioritise traffic in the event it becomes congested, thus unequally sharing the delay and loss effects. Priority colouring is generally assigned based on some policy. Some customers want differentiated service, but they cannot say precisely how differentiated it should be, only expecting a marked improvement. Other customers expect operators to offer an assurance, albeit statistical, that the effects of congestion will be avoided for certain of their traffic. Of course, a network cannot offer open-ended assurances for any level of applied load or for any distribution of that load across network destinations; customers who want assurances must have some idea of the traffic profile they would like assured. Differentiated services solutions aim to improve on earlier techniques which partition capacity for each customer's requirements at every resource. They handle traffic in classes, rather than more costly per-customer virtual circuits.
Bandwidth reservation: Just as shadow pricing has been used across core networks to synthesise differentiated service at the edge, it can also be used to synthesise connection admission control. The admission control may be determined on end systems or at the network edge. Congestion may be metered at the egress of a ring of gateways, thereby controlling session admission into a potentially Internet-wide edge-to-edge hop. However a congestion report needs to be fed back across one large RSVP hop. This effectively creates a feedback channel to an upstream router using only standard Internet signalling protocols.
Retail congestion pricing: All the above uses of shadow pricing convert it into a dynamic service penalty, whether reduced rate, reduced priority, or increased blocking probability. The original formulation of shadow pricing was, however, largely framed around the idea that customers would be charged dynamic prices, which they would handle with a policy-driven software agent. It has been argued that the service models that network operators choose to offer will always support current applications, whereas congestion pricing in the retail market will allow new applications with new QoS requirements to evolve. Despite general aversion to the unpredictability of congestion pricing, there is still scope for pure retail congestion pricing, particularly targeted at machine mediated applications like peer-to-peer file-sharing, remote data back-up, etc., as well as at corporate users (e.g. content delivery network operators) more interested in cost saving, than short-run predictability. All the more recent congestion pricing schemes have proposed the ECN mark as the shadow price.
If the sender is to be exposed to congestion charges based on standard ECN, the sender's network operator would not reliably be able to meter end-to-end congestion feedback. The receiver's network operator would have adopt a scheme such as metering accumulated path congestion notification then transfer charging the sender (variants of this charging model exist but none solve the problem). Without a global solution to source spoofing, an unavoidable ‘denial of funds’ problem results, where malicious senders can cause charges to innocent receivers. Similarly, if ECN-based congestion charging were used at network interconnect points, downstream networks would have to pay upstream networks for upstream congestion, despite having only indirect control over upstream networks' routing.
Congestion Control Incentive Mechanisms
Without incentives, congestion control contains inherent ‘free-rider’ problems. The rules for fair resource allocation during congestion don't match what every end user would do if given free choice to act in their own self-interest. Network providers may also have incentives to cheat given that they are generally in competition with each other, and that they would like their customers to pay more for less wherever possible.
Two main types of self-interest can be identified:                Users wanting to transmit data between themselves across the network as fast as possible and pay as little as possible for the privilege. In this respect, there is no distinction between senders and receivers;        Network operators wanting to maximise the revenues they extract from the resources they choose to invest in. They have to compete amongst themselves for the custom of end systems.        
An aim of certain embodiments of the present invention is to allow nodes in a network to use characterisation information received with or in respect of data items, for example path characterisation information of the type referred to above in relation to the un-published co-pending UK patent applications, in order to subject some data items to a process other than the normal process to which data items are subjected by that node. More particularly, certain embodiments of the invention allow nodes, such as routers in the network, to identify items such as data packets whose associated characterisation information has been assigned, changed, or otherwise set in such a way as to gain an unfair advantage. Such items can be thought of as having been received from ‘misbehaving flows’.